from typing import List

import sortedcontainers


class SummaryRanges:
    def __init__(self):
        self.seg = sortedcontainers.SortedList()

    def addNum(self, val: int) -> None:
        if self.seg:
            left = self.seg.bisect_left([val, val])
            right = self.seg.bisect_right([val, val])
            if left == right and left > 0:
                left -= 1
            if ((left < len(self.seg) and self.seg[left][1] == val - 1) and
                    (right < len(self.seg) and self.seg[right][0] == val + 1)):  # 左右正好连接一个两个区间
                new = [self.seg[left][0], self.seg[right][1]]
                self.seg.pop(right)
                self.seg.pop(left)
                self.seg.add(new)
            elif left < len(self.seg) and self.seg[left][1] == val - 1:  # 左侧连接一个区间
                new = [self.seg[left][0], self.seg[left][1] + 1]
                self.seg.pop(left)
                self.seg.add(new)
            elif right < len(self.seg) and self.seg[right][0] == val + 1:  # 右侧连接一个区间
                new = [self.seg[right][0] - 1, self.seg[right][1]]
                self.seg.pop(right)
                self.seg.add(new)
            elif (left < len(self.seg) and self.seg[left][0] <= val <= self.seg[left][1] or
                  (right < len(self.seg) and self.seg[right][0] <= val <= self.seg[right][1])):  # 包含在一个区间内
                return
            else:
                self.seg.add([val, val])
        else:
            self.seg.add([val, val])

    def getIntervals(self) -> List[List[int]]:
        return list(self.seg)


if __name__ == "__main__":
    obj = SummaryRanges()
    obj.addNum(1)
    print(obj.getIntervals())  # [1, 1]
    obj.addNum(3)
    print(obj.getIntervals())  # [1, 1], [3, 3]
    obj.addNum(7)
    print(obj.getIntervals())  # [1, 1], [3, 3], [7, 7]
    obj.addNum(2)
    print(obj.getIntervals())  # [1, 3], [7, 7]
    obj.addNum(6)
    print(obj.getIntervals())  # [1, 3], [6, 7]
